Resorts and hotels
Since Kenting's popularity as a destination is rising, it seems like every plot of land that isn't already a hotel or restaurant is being turned into one, and many shops and restaurants have rooms upstairs too, so it shouldn't be too hard to find a place to sleep. The newer hotels are generally nicer but pricier, and you'll want to check there's no ongoing construction that might interfere with your sleep.
The main resort hotel in Kenting is "Château Beach Resort", made famous by the movie "Cape No.7" - it is also the only hotel in the area with direct beach access from terraced rooms.
Lodging
The Surf Shack Hostel
The Surf Shack Bar, Grill and Hostel is located in Hengchun Town in southern Taiwan. It's a 15min drive north from the tourist town of Kenting. The hostel can arrange scooter and offers a western style restaurant on the first floor with 5 rooms on the second and third floors. There is a large balcony with mountain view on the 3rd floor. Also offers surf lessons, surf tours, surfboard rentals and scuba diving tours in the local tropical waters.
Ipanema Surf House
camping
Camping is allowed in the National Park. It is advisable to contact the park directly to setup permits. Several bed and breakfast or small proprietor operations will rent tents and space for camping on their property.